![]() ファイルシステムにおけるファイル管理・編集方法及び装置
专利摘要:
ファイルシステムにおけるファイルの管理・編集方法及び装置を提供する。ファイルシステムにおけるファイルのデータ管理方法では、前記ファイルのデータを格納する記憶スペースはサイズが同じで順次に付番された複数のブロックに分割され、前記ブロックは順次に付番されたチャンクで構成される。各チャンクは少なくとも1つのブロックを有する。1つのチャンクに対して、前記ファイル中のデータを削除する段階の後に、第1の管理データと第2の管理データとを用いて、各チャンクの前記最初のブロックの先頭部分と、前記最後のブロックの終わり部分とにある、データにより占有されていないスペースのサイズを記録する。前記スペースのサイズは前記ブロックのサイズより小さい。 公开号:JP2011508326A 申请号:JP2010540087 申请日:2008-11-19 公开日:2011-03-10 发明作者:ジャン,シャオ・ロン;フー,ジアン・チアン 申请人:トムソン ライセンシングThomson Licensing; IPC主号:G06F12-00
专利说明:
[0001] 本発明はパーソナルビデオレコーダ(PVR)などのファイル記憶装置の分野に関する。より具体的には、本発明はファイルシステムにおけるファイル管理・編集方法及び装置に関する。] 背景技術 [0002] 近年、セットトップボックスのパーソナルビデオレコーダ(PVR)アプリケーションが広く使われている。ユーザはビデオ記録物(video records)を編集しなければならない場合がある。例えば、ファイルを削除してコマーシャルを除去する必要がある。しかし、コマーシャルはビデオ記録物のどこにあるか分からず、ユーザはビデオ記録ファイル(video record files)のどこかからデータを削除する必要が生じる。すなわち、ユーザはビデオ記録ファイルの始め、途中、または終わりからコマーシャルを除去する必要がある。] [0003] 図1は、FAT32やEXT2などの従来のファイルシステムの一例である。このファイルシステムでは、ファイルは複数のブロックに格納される。図1では、10ブロックを用いてファイルを格納している。1ブロックは最小のアロケーション単位(allocation unit)であり、16セクタを含む。1セクタは512バイトであり、通常、ブロックの大きさは8Kバイトである。シーケンシャルファイルでは、全てのブロックはファイル管理システムでリンクされている。各ブロックにおいて、リンク情報は、カレントブロックの前のブロックのナンバなどの前インデックス(previous index)と、カレントブロックの後のブロックのナンバなどの後インデックス(next index)とを含む。通常、ファイル管理システムは、ファイルが始め、すなわち始めのブロックのナンバと、ファイルが占める記憶空間(space)の長さ、すなわちいくつのブロックを用いてこのファイルを格納しているかとを知っている。ファイルの実際の長さは、そのファイルが占める記憶空間の長さより短くてもよい。] 図1 [0004] この従来のファイルシステムでは、ファイルの終わりからデータを削除し、例えばコマーシャルを除去するのは容易である。ファイルの終わりで削除すると、削除されたデータは直接解放される。しかし、ファイルの途中からデータを削除するのは困難であり、特に複数のブロックからその一部を削除するのは困難である。ブロックの一部からデータを削除するとき、そのブロックは完全なブロックではなくなる(不完全)。すなわちそのブロックのデータは8K未満となる。この状態では、従来の方法では、後続のブロックのデータをシフトして、不完全ブロックにデータを入れる(fill)。その理由は、従来のファイルシステムでは、始めのブロックのナンバとファイルの長さ(すなわち、ブロックをいくつ用いてファイルを格納するか)とのみを登録するだけだからである。そのため、ブロックからデータを除去しただけでも、そのブロックのその部分を読み出すのに時間がかかってしまう。しかし、後続のブロックをシフトして不完全ブロックにデータを入れるには処理時間がかかり、特に大きなファイルの場合は処理時間がかかる。] [0005] 従来のファイルシステムにある問題を解決するため、特許文献1には、ビデオ/オーディオデータの編集において、媒体に対する読み出し/書き込みアクセスに伴うコピー動作を低減して、高速編集を実現する情報編集コントローラが開示されている。] 先行技術 [0006] 特開2003−052006号公報] 課題を解決するための手段 [0007] 一態様では、ファイルシステムにおけるファイルのデータ管理方法を提供する。該ファイルシステムでは、ファイルのデータを格納する記憶スペースが、サイズが同じで順次に付番された複数のブロックに分割される。前記ブロックは順次に付番されたチャンクにより構成され、各チャンクは少なくとも1つのブロックを有する。前記方法は、1つのチャンクに対して、前記ファイル中のデータを削除する段階の後に、第1の管理データと第2の管理データとを用いて、各チャンクの前記最初のブロックの先頭部分と、前記最後のブロックの終わり部分とにある、データにより占有されていないスペースのサイズを記録する段階を有する。前記スペースのサイズは前記ブロックのサイズより小さい。] [0008] 一実施形態では、前記チャンクの先頭部分または終わりの部分からデータを削除する段階を有する。] [0009] 詳細な一実施形態では、ファイルのデータを有する複数のチャンクがリンクされ、リンク情報がファイルシステム管理データに記録される。] [0010] さらに、1つのチャンクが完全に削除されたとき、削除されたチャンクの記憶スペースを解放し、削除されたチャンクの前と後のチャンクをリンクする。] [0011] 第2の態様では、ファイルシステムにおけるファイルのデータ管理方法を提供する。該ファイルシステムでは、ファイルのデータを格納する記憶スペースが、サイズが同じで順次に付番された複数のブロックに分割される。前記ブロックは順次に付番されたチャンクにより構成され、各チャンクは少なくとも1つのブロックを有する。前記方法は、1つのチャンクに対して、前記ファイル中のデータを削除する段階の後に、第1の管理データと第2の管理データとを用いて、各チャンクの前記最初のブロックの先頭部分と、前記最後のブロックの終わり部分とにある、データにより占有されていないスペースのサイズを記録する段階を有する。前記スペースのサイズは前記ブロックのサイズより小さい。前記ファイルの一部が削除され、その削除の開始位置と終了位置とが同一ブロックではないが同一チャンク中にあるとき、前記チャンクを新しい第1のチャンクと新しい第2のチャンクとに分割する。この場合、第3の管理データと第4の管理データとを用いて、前記新しい第2のチャンクの最初のブロックの先頭部分と最後のブロックの終わりの部分との空のスペースのサイズを記録し、前記新しい第1のチャンクと新しい第2のチャンクとをリンクして前記ファイルの連続性を保つ。] [0012] 一実施形態では、前記新しい第1のチャンクは削除前の最初のチャンクの番号を用いて付番され、前記新しい第2のチャンクは前記ファイルシステムの元の最後のチャンクに続く付番をされる。] [0013] 他の一実施形態では、1つのブロックのデータを完全に削除したとき、前記ブロックのスペースを解放する。] [0014] 第3の態様では、ファイルシステムにおけるファイルのデータ管理方法を提供する。該ファイルシステムでは、ファイルのデータを格納する記憶スペースが、サイズが同じで順次に付番された複数のブロックに分割される。前記ブロックは順次に付番されたチャンクにより構成され、各チャンクは少なくとも1つのブロックを有する。前記方法は、1つのチャンクに対して、前記ファイル中のデータを削除する段階の後に、第1の管理データと第2の管理データとを用いて、各チャンクの前記最初のブロックの先頭部分と、前記最後のブロックの終わり部分とにある、データにより占有されていないスペースのサイズを記録する段階を有する。前記スペースのサイズは前記ブロックのサイズより小さい。前記ファイルのデータの一部を1つのチャンクの1つのブロックの途中から削除したとき、前記ブロックの削除されたデータに続くデータの残っている後半を前記ブロックのデータの前半の直後の位置に移動し、前記チャンク中の削除をしたブロックとその前のブロックとを新しい第1のチャンクとして再構成し、削除をしたブロックの後にブロックがあれば、そのブロックを新しい第2のチャンクとして再構成し、第3の管理データと第4の管理データとを用いて、前記新しい第2のチャンク中の最初のブロックの先頭部分と、最後のブロックの終わりの部分との空きスペースのサイズをそれぞれ記録し、前記新しい第1のチャンクと新しい第2のチャンクとをリンクする。] [0015] 一実施形態では、前記新しい第1のチャンクは削除前の最初のチャンクの番号を用いて付番され、前記新しい第2のチャンクは前記ファイルシステムの元の最後のチャンクに続く付番をされる。] [0016] 他の一実施形態では、ファイルシステム管理データに前記チャンクのリンク情報を記録する。] [0017] 第4の態様では、ファイルシステムを説明する。該ファイルシステムでは、ファイルのデータを格納する記憶スペースが、サイズが同じで順次に付番された複数のブロックに分割される。前記ブロックは順次に付番されたチャンクにより構成され、各チャンクは少なくとも1つのブロックを有する。前記ファイルシステムは、各チャンクの先頭部分及び/または終わり部分の空き記憶スペースのサイズを示す、そのチャンクの管理データであって、前記空き記憶スペースはブロックのサイズより小さい管理データを有する。] [0018] 一実施形態では、前記チャンクの最初のブロックの先頭部分と最後のブロックの終わり部分のスペースのサイズを、第1の管理データと第2の管理データにより記録する。] [0019] 他の一実施形態では、ファイルの全チャンクがリンクされて前記ファイルの連続性を保ち、リンク情報をファイルシステム管理データに記録する。] [0020] 第5の態様では、上記のファイルシステムを含む記憶装置を説明する。] 図面の簡単な説明 [0021] 従来のファイルシステムを示す図である。 本ファイルシステムの一実施形態を示す図である。 本ファイルシステムの他の一実施形態を示す図である。 本実施形態によるファイルシステムを用いた読み出し動作の実行時に、チャンク中の実際のデータサイズをいかに計算するか示すフローチャートである。 本ファイルシステムからの読み出し動作例を示すフローチャートである。 本ファイルシステムからの書き込み動作の実行時に、チャンク中の実際のデータサイズをいかに計算するか示すフローチャートである。 本ファイルシステムへの書き込み動作例を示すフローチャートである。 本ファイルシステムにおけるデータ除去動作例を示すフローチャートである。 チャンクの始めからデータを切り取るデータ除去動作例を示す図である。 チャンクの終わりからデータを切り取るデータ除去動作例を示す図である。 チャンクの途中からデータを切り取るデータ除去動作を示すフローチャートである。 チャンクの始めからデータを切り取るデータ除去動作例を示す図である。] 発明の実施するための形態 [0022] ここに説明する例は本発明の好ましい実施形態を説明するものであり、かかる例が本発明の範囲を限定するものと解してはならない。] [0023] 一実施形態では、図2に示したように、ファイルは8ブロックよりなり、各ブロックは8Kバイトのデータを含む。ファイル管理システムでは、ファイルに属するブロックはチャンクとして管理される。チャンクはブロック(少なくとも1つのブロック)のグループよりなる。図2において、チャンク0はブロック0−2よりなり、チャンク1はブロック10−11よりなり、チャンク2はブロック12−14よりなる。本実施形態では、すべてのチャンクのブロック数は異なるが、実施形態によっては同じでもよい。本実施形態では、6つの記述子を用いて各チャンクを記述する。6つの記述子とは、StartBlockNumber、TotalBlockNumber、PreviousChunkNumber、NextChunkNumber、UnusedSizeInFirstBlock、UnusedSizeInLastBlockである。StartBlockNumberはチャンクの始めのブロックのナンバを示す。TotalBlockNumberはチャンクの総ブロック数を示す。PreviousChunkNumberはカレントチャンクの前のチャンクのナンバを示す。NextChunkNumberはカレントチャンクの後のチャンクのナンバを示す。UnusedSizeInFirstBlockはチャンクの最初のブロックの未使用記憶空間量(データが占めていない記憶空間のバイト数)を示す。UnusedSizeInLastBlockはチャンクの最後のブロックの未使用記憶空間量(データが占めていない記憶空間のバイト数)を示す。最後の2つの記述子を使う理由は、チャンクを途中で削除すると、最後のブロックの未使用記憶空間がそのブロックにおいて削除を始めるところとして現れ、最初のブロックの未使用記憶空間がそのブロックにおいて削除を終えるところとして現れるからである。] 図2 [0024] 図2を参照するに、チャンク0−2はそれぞれ(0,3,−1,1,0,0)、(10,2,0,2,0,0)、(12,3,1,−1,0,0)と記述されている。第1のチャンクの記述子は(0,3,−1,1,0,0)である。第1の記述子「0」は、カレントチャンクがブロック0から始まることを示す。第2の記述子「3」は、カレントチャンクにはブロックが3つあることを意味する。第3の記述子「−1」は、(カレントチャンクがファイルの最初のチャンクなので、)カレントチャンクの前のチャンクがNULLであることを示す。第4の記述子「1」は、カレントチャンクに続くチャンクがチャンク1であることを意味する。第5の記述子「0」と第6の記述子「0」とは、カレントチャンクの最初のブロックの未使用スペースが0バイトであり、カレントチャンクの最後のブロックの未使用スペースが0バイトであることを示し、これはチャンク0のすべてのブロックが8Kバイトのデータを含むことを意味する。チャンク1とチャンク2の記述子はチャンク0の記述子と同様である。本実施形態では、「NULL」を用いて、カレントチャンクと比較して前または次のチャンクのインデックスが無効であることを示し、これはカレントチャンクがファイルの最初のチャンクか最後のチャンクのいずれかであることを意味する。例えば、チャンク0の前のチャンクのインデックスは「NULL」であり、チャンク2の次のチャンクのインデックスも「NULL」である。] 図2 [0025] 図3に示した他の例では、ファイルにはチャンク0、チャンク1、チャンク2の3つのチャンクがあり、それぞれ(10,2,−1,1,1024,2048)、(20,4,0,2,0,0)、(28,6,1,−1,0,0)と記述される。これら3つのチャンクの記述子から分かることは、チャンク0がブロック10から始まり、その長さが2ブロックで、各ブロックは8K(8×1024)バイトであり、チャンク0の最初のブロックの未使用スペースの大きさは1K(1024)バイトであり、チャンク0の最後のブロックの未使用スペースの大きさは2K(2048)バイトであることである。第2のチャンクはブロック20から始まり、その長さは4ブロックで、各ブロックは8K(8×1024)バイトであり、カレントチャンク1の最初と最後のブロックの未使用スペースの大きさは0で、これはチャンク1にはデータが詰まっていることを意味する。第3のチャンクはブロック28から始まり、その長さは6ブロックで、各ブロックは8K(8×1024)バイトであり、カレントチャンク2の最初と最後のブロックの未使用スペースの数は0である。] 図3 [0026] 図4と図5は、本実施形態による読み出し動作プロセスを詳細に示す。] 図4 図5 [0027] 図4は、チャンク中のデータの実際の長さまたは大きさの計算プロセスを示すフローチャートである。本プロセスはステップ410から始まる。ステップ420において、チャンク中の実際のデータの長さChunkLengthを計算する。ChunkLength=TotalBlockNumber*BlockSize−UnusedSizeInFirstBlock−UnusedSizeInLastBlock、ここでTotalBlockNumberはカレントチャンク中のブロックの総数である。TotalBlockNumberに各ブロックの大きさBlockSize(バイト)をかけると、カレントチャンクが占める総バイト数が得られる。一方、カレントチャンクが占める総バイト数からUnusedSizeInLastBlockとUnusedSizeInFirstBlockとを除く必要がある。これらのスペースは実際には空だからである。よって、ステップ430でカレントチャンクが決定され、それがファイルの最後のチャンクでなければ、カレントチャンク中の実際のデータの長さが求まる。本プロセスはステップ460で終わる。例えば、チャンク0のChunkLengthは2×8K−1K−2K=13Kバイトである。] 図4 [0028] しかし、ステップ430の判断がYESであれば、プロセスはステップ440に進み、さらに、カレントチャンクを占めるカレントファイルの実際のデータの長さを決定する。このステップを用いて最後のチャンク中の予約スペースを排除する。ファイルシステムにデータが書き込まれると、そのデータを収容するためにより大きなスペースが割り当てられる。カレントデータの後に同じファイルにさらに別のデータが書き込まれたとき、スペースの再割り当てはされない。予約サイズを削除するためにステップ440が必要である。ステップ440では、ChunkLengthがFileLengthとChunkStartPositionの差より大きいか判断する。FileLengthはカレントファイルに何バイトのデータがあるか示すパラメータであり、ChunkStartPositionはカレントチャンクがどこから始まるか、またはカレントチャンクの前に何バイトのデータがあるかを示す。図3のチャンク2を例に取る。チャンクの長さは6×8K=48Kである。FileLengthは(4+6+2)×8K−3K=93Kである。チャンク2の始めの位置ChunkStartPositionは2×8K+4×8K−1K−2K=45Kバイトである。すなわち、ファイルのチャンク2に格納された部分は、そのファイルの始めから45Kだけオフセットされて始まる。ステップ440における判断がYESの場合、すなわちChunkLengthがFileLengthとChunkStartPositionとの差より大きい場合、ChunkLength分のデータを読み出し、残りのデータはここでは考慮しない。] 図3 [0029] 図5は読み出しプロセスの例を説明するフローチャートである。] 図5 [0030] 読み出しプロセスはステップ510において始まり、ステップ511において、読み出すデータの長さが0より大きいか判断する。これは妥当性チェックである。判断結果がNOであれば、これは読み出すデータが無いことを意味する。次に、フローチャートはステップ512に進み、終了する。読み出すデータがあれば、プロセスはステップ513に進み、ファイルを読み出す準備としてパラメータを計算する。ステップ513において、OffsetInChunkを最初に計算する。これはカレントチャンクにおける読み出し動作のオフセットを示すポインタである。例えば、チャンク中のデータの第1のバイトのオフセットは「0」バイトであり、チャンク中のデータの第2のバイトのオフセットは「1」バイトであり、以下同様である。OffsetInChunk=FilePosition−ChunkStartPositionである。FilePositionはファイルにおけるオフセットである。例えば、ファイル中のデータの第1のバイトのオフセットは「0」バイトであり、ファイル中のデータの第2のバイトのオフセットは「1」バイトであり、以下同様である。また、図3のチャンク0を例に取る。ファイルがチャンク0のデータの第1のバイトから読み出される。チャンク0のデータの第1のバイトはファイルのデータの第1のバイトでもあるので、FilePositionは0、ChunkStartPositionは0、そのためOffsetInChunkも0である。ファイルをデータの第5のバイトから読み出すとき、FilePositionは5バイトであり、ChunkStartPositionは0バイトである。そのためOffsetInChunkは5バイトである。次に、チャンク1のデータの第1のバイトの物理的位置を計算する。これは、ReadOffset=ChunkStartAddressInHardDisk+OffsetInChunk+UnusedSizeInFirstBlockである。ChunkStartAddressInHardDiskはハードディスク上のカレントチャンクのアドレスである。よって、チャンク1の場合、UnusedSizeInFirstBlockは1Kバイトであり、ReadOffsetはChunkStartAddressInHardDisk+1Kバイトである。すなわち、アプリケーションはチャンク1の物理的位置を求め、1Kバイトオフセットして、読み出すデータの実際の位置を求める。また、カレントチャンクからどれだけのデータを読み出せるか判断する:AvailableSizeInChunk=ChunkLength−OffsetInChunk。チャンク1では、AvailableSizeInChunkは13Kバイトである。] 図3 [0031] さらにステップ514において、読み出すデータ量Length_to_Readがカレントチャンク中のデータAvailableSizeInChunkより大きいか判断する。このステップを用いてカレントチャンクから読み出せば十分か判断する。さらにデータを読み出さねばならない場合、すなわちステップ514においてYESの場合、まずカレントチャンク中のデータをすべて読み出さねばならない。ステップ515において、ReadSizeInChunk=AvailableSizeInChunkと設定する。ステップ514における判断がNOであれば、読み出すデータが、カレントチャンク中のデータ量より小さいことになり、フローチャートはステップ516に進み、Length_to_ReadをReadSizeInChunkに設定する。ステップ515と516の後、プロセスはステップ517に進み、読み出し動作を行い、ReadOffsetの位置からデータのReadSizeInChunkを読み出す。読み出し動作後、プロセスはステップ518に進み、パラメータLength_to_ReadとFilePositionとを更新する。データのReadSizeInChunkは上記のプロセスごとに読み出されるので、Length_to_ReadはLength_to_Read−ReadSizeInChunkに更新される。FilePosition=FilePosition+ReadSizeInChunkである。] [0032] さらに、ステップ519において、ファイルのデータがすべて読み出されたか判断する。判断結果がYESであれば、すなわち更新したLength_to_Readが0より大きければ、読み出されていないデータがまだある。ステップ520と521において、アプリケーションは次のチャンクに行き、その後の読み出しプロセスを実行する。また、ステップ521において、ChunkStartPositionが前のChunkStartPositionプラス前のChunkLengthに更新される。これは次のチャンクのChunkStartPositionである。ステップ519の判断結果がNOであれば、カレントファイルのデータはすべて読み出されているので、ステップ522においてプロセスが終了する。] [0033] 図6と図7を参照して、書き込み動作の例を説明する。図4と図5で用いた記号、ラベル、識別子はこれ以上説明しない。] 図4 図5 図6 図7 [0034] 図6は、チャンクにデータを書き込むときに使える空きスペースの量の計算を示すフローチャートである。本プロセスはステップ601から始まる。ステップ602において、カレントチャンク中の実際のデータの長さを決定する。このステップは図4の読み出しプロセスにおける動作と同様であり、ここでは説明を省略する。次に、ステップ603において、カレントチャンクがファイルの最後のチャンクか判断する。判断結果がNOであれば、プロセスはステップ605に進み、終了する。判断結果がYESであれば、プロセスはステップ604に進み、カレントチャンク中の空きスペースはステップ602で求めた値にファイルの最後のチャンクのUnusedSizeInLastBlockの値を足したものである。] 図4 図6 [0035] 図7には書き込みプロセスの詳細を示した。] 図7 [0036] 書き込みプロセスはステップ710から始まり、次にステップ712に進み、書き込むデータの長さが有効であるか判断する。判断結果がNOであれば、プロセスはステップ712に進み、終了する。YESであれば、プロセスはステップ713に進み、カレントチャンクにおける書き込み位置と、ハードディスクにマッピングした位置と、カレントチャンクに何バイトのデータを書き込めるかとを計算する。これらの3つの値をOffsetInChunk、WriteOffset、AvailableWriteSizeInChunkで表す。ここでのOffsetInChunkの計算は読み出しプロセスにおけるものと同じである。しかし、ここでのOffsetInChunkは、カレントチャンクにおいて書き込みプロセスが始まる位置の計算に用いられる。WriteOffsetはカレントファイルを書き込む実際の物理的位置を示し、その計算プロセスは図4の読み出しプロセスにおけるReadOffsetと同様である。AvailableWriteSizeInChunkはカレントチャンクに書き込めるサイズを示す。これの計算プロセスは、ChunkLengthを図6のプロセスを用いて計算すること以外は、読み出しプロセスにおけるAvailableSizeInChunkと同様である。ステップ714において、データを書き込めるスペースがカレントチャンクにあるか、すなわちAvailableWriteSizeInChunkが0より大きいか判断する。NOであれば、プロセスはステップ720に進み、次のチャンクを使えるか検討する。ステップ714における判断がYESなら、次にステップ715において、書き込むデータの長さLength_to_Writeが、書き込み動作に使えるサイズAvailableWriteSizeInChunkより大きいか判断する。ステップ715における判断がYESであり、すなわちカレントチャンクに書き込めるサイズが書き込むデータに対して足りなければ、他のチャンクが必要となる。プロセスはステップ716に進み、サイズがAvailableWriteSizeInChunkのデータを、ステップ718の書き込み動作で用いるWriteSizeInChunkに設定する。判断結果がNOであれば、カレントチャンクに書き込むデータに対し十分なスペースがあることになる。ステップ717において、Length_to_WriteをWriteSizeInChunkに設定し、プロセスはステップ718に進み、WriteSizeInChunkのサイズのデータをWriteOffsetの位置から書き込む。] 図4 図6 [0037] 順次、元のFilePositionは、元のFilePosition+WriteSizeInChunkによって決まる位置に動く。ファイルの残りの書き込みデータのサイズは、元のLength_to_Writeから(すでにチャンクに書き込まれた)WriteSizeInChunkを引いたものに変更される。] [0038] ステップ715の判断結果によって後続の書き込みプロセスでチャンクがもっと必要となり得るので、ステップ720において、書き込むデータがまだあるか判断する。答えがYESであれば、ステップ721と722に示したように、次のチャンクに移って書き込みプロセスを実行する。ステップ724において、UnusedSizeInFirstBlockとUnusedSizeInLastBlockを0に初期化して次のチャンクに移る。書き込み動作が始まる位置をChunkStartPosition=ChunkStartPosition+ChunkLengthに変更する。] [0039] もう一つ重要なプロセスがある。それはファイルシステムからのデータの削除である。この重要なプロセスを図8乃至図11に示した。] 図11 図8 [0040] 図8は削除プロセスの例を示すフローチャートである。このプロセスはステップ801から始まる。ステップ802において、削除を開始する位置を見つける判断をする。このステップは妥当性チェックプロセスである。その後、削除するデータの長さが有効な値であるか判断する(ステップ803)。NOであれば、プロセスは805に進み、終了する。YESであれば、ステップ804において、削除を始める位置OffsetInChunkと、カレントチャンクから削除するデータの長さとを決定する。OffsetInChunkを式OffsetInChunk=FilePosition−ChunkStartPositionを用いて計算し、AvailableDeleteSizeを式AvailableDeleteSize=ChunkLength−OffsetInChunkを用いて計算する。次に、プロセスはステップ806に進み、削除するデータの長さLength_to_Deleteが可憐とチャンク中のデータのサイズより小さくないか判断する。ステップ806における判断結果がNOであれば、カレントチャンクには削除するのに十分なデータがあることになる。次に、プロセスはステップ813−816に進み、削除動作を実行する。] 図8 [0041] ステップ813において、OffsetInChunkが0であるか判断する。このステップは、削除プロセスがチャンクのデータの最初のバイトから始まるか判断するものである。判断結果がNOである場合、すなわちカレントチャンクの削除動作がカレントチャンクの途中から始まる場合、プロセスはステップ815に進み、OffsetInChunkが示す位置からカレントチャンクのデータを削除する。同時に、ステップ806の判断結果がNOなので、カレントチャンクには削除が必要なデータより長いデータがあり、データの一部が残る。この場合、ステップ815においてカレントチャンクの中心部のみを削除し、プロセスはステップ816で終了する。ステップ813の判断結果がYESであれば、削除動作がカレントチャンクの始めから始まる。ステップ806の判断結果は否定なので、削除するデータ量よりも多いデータがあり、図テップ814においてカレントチャンクの先頭部分が削除される。削除動作をカレントチャンクの先頭部分から行うとき、残りのカレントブロック中の最初のブロックの先頭部分が部分的に削除され得る。このブロックはデータが部分的に入ったブロックになる。言い換えると、このブロックはそろっていない(not aligned)。新しいUnusedSizeInFirstBlockは、カレントチャンクに残っている最初のブロックの、使用されていない先頭部分のサイズを表す。新しいUnusedSizeInFirstBlockは次の関数を用いて計算する:UnusedSizeInFirstBlock=(Length_to_Delete+UnusedSizeInFirstBlock)%BlockSize。(Length_to_Delete+UnusedSizeInFirstBlock)は解放されるエリアの長さを示す。演算「%」は割り算の余りを求めるものである。余りが0でなければ、削除後に残ったチャンクの最初のブロックの先頭部分に、データで占められていないスペースがあることになる。図9に例を示した。] 図9 [0042] 図9において、カレントチャンクには5つのブロック1〜5がある。ブロック1の先頭に3Kバイトの不使用スペースがあり、ブロック5の終わりに2Kバイトの不使用スペースがある。すなわち、カレントチャンクのUnusedSizeInFirstBlockは3Kバイトであり、カレントチャンクのUnusedSizeInLastBlockは2Kバイトである。削除はブロック1の最初のデータから始まり、18Kバイトのデータが削除される。Length_to_Deleteは18Kバイトである。削除後、ブロック1−2は完全に削除されるので解放され、削除後のチャンクのUnusedSizeInLastBlockは削除前の元のチャンクのUnusedSizeInLastBlockと同じであり、UnusedSizeInFirstBlockは(Length_to_Delete+UnusedSizeInFirstBlock)%BlockSize=(18+3)%8=5Kバイトに変わる。] 図9 [0043] ステップ806の判断結果が肯定であれば、カレントチャンクを全部削除しても足りない。この場合、プロセスはステップ807に進み、カレントチャンクの削除を始めからするか、途中からするか判断する。判断結果が否定であれば、削除動作はカレントチャンクのどこか途中から行われ、プロセスはステップ808に進み、チャンクのOffsetInChunkの位置からスペースの削除を行う。ステップ806の判断結果はYESであり、カレントOffsetInChunkからのデータを削除すること、及びチャンクの始めのデータは一部が残っていることを示しているので、カレントチャンクのUnusedSizeInFirstBlockとデータのサイズOffsetInChunkの総数がブロック全体(8Kバイト)でない場合、カレントチャンクの終わりに不使用スペースがあるはずである。そこで、ステップ808において、次の関数UnusedSizeInLastBlock=BlockSize−(OffsetInChunk+UnusedSizeInFirstBlock)%BlockSizeを用いてカレントチャンクの新しいUnusedSizeInLastBlockを計算する。ここで、OffsetInChunk+UnusedSizeInFirstBlockはチャンクにデータが残っていることを意味する。演算「%」は割り算のあまりを求めるものである。演算「%」の後、新しい最終ブロックのデータの残り量を求める。それをBlockSizeから差し引き、最終ブロックの不使用サイズを求める。図10はこのプロセスを示す例である。] 図10 [0044] 図10において、カレントチャンクには5つのブロック1〜5がある。ブロック1の先頭部分には不使用スペースが5Kバイトあり、ブロック5の終わり部分には不使用スペースが3Kバイトある。UnusedSizeInFirstBlockは5Kバイトであり、UnusedSizeInLastBlockは3Kバイトである。削除はブロック3の6Kバイトのところから始まり、15Kバイトのデータが削除される。OffsetInChunkは17Kバイトである。削除後、ブロック4−5は解放され、カレントチャンクのUnusedSizeInFirstBlockは変わらず、UnusedSizeInLastBlockの値は新しくなる。この新しい値はBlockSize−(OffsetInChunk+UnusedSizeInFirstBlock)%BlockSize=8K−((17+5)%8)K=8K−6K=2Kバイトである。] 図10 [0045] しかし、ステップ807の判断結果が肯定であれば、削除動作がカレントチャンクの始めから始まる。ステップ806からステップ807に進むのはYESの場合なので、ステップ809においてチャンク全体が削除される。この動作の後、プロセスは次のチャンクに進み、ステップ803に戻る。] [0046] 図8の削除がチャンクの中央部分の削除、すなわちステップ815のプロセスである場合、チャンクは2つのチャンクに分かれる。図11はこの条件を処理する動作を示す。本プロセスはステップ1111から始まる。ステップ1112において、Offset=OffsetInChunk+UnusedSizeInChunkにより記述子「Offset」を計算する。次に、ステップ1113において、チャンクの同じブロックに対して削除を実行するか、すなわちブロックの中央部分を削除するか判断する。判断方法は、(Offset/BlockSize)=(Offset+Length_to_Delete)/BlockSizeであるか判断するものである。ここで、「/」は結果の整数部を求める演算である。ステップ1113の判断がNOであれば、チャンクのブロックがいくつか全体としてカレントチャンクの中央部分から削除されることになり、カレントチャンクは2つのチャンクに分かれる。ステップ1113の判断が肯定であれば、削除動作はブロックの中央部分で起こる。プロセスはステップ1114に進み、ブロックの後の部分をコピーして、削除するコンテンツを上書きするのに用いられる。Offsetの値は、元のOffsetの値に(BlockSize−(Offset+Length_to_Delete)%BlockSize)を加えた値で更新される。ステップ1115の後、ステップ1116とステップ1117において一部の識別子の値を更新する。] 図11 図8 [0047] 新しいチャンクの記述子を設定し、元のチャンクの記述子の一部をステップ1116とステップ1117において変更する。] [0048] ステップ1116と1117のプロセスを図12を参照してさらに説明する。図12において、カレントチャンク、例えばチャンク5には、6つのブロックがある。StartBlockNumerはブロック10であり、TotalBlockNumberは6ブロックであり、PreviousChunkNumberはチャンク4であり、NextChunkNumberはチャンク6であり、UnusedSizeInFirstBlockは3Kバイトであり、UnusedSizeInLastBlockは4Kバイトである。] 図12 [0049] 削除動作を実行するとき、OffsetInChunkは15Kバイトであり、Length_to_Deleteは21Kバイトである。これは15Kバイトより後の位置から21Kバイトのデータが削除されることを意味する。そのため、OffsetはOffsetInChunk+UnusedSizeInFirstBlock=15K+3K=18Kバイトである。ステップ1113によると、(Offset/Block)=(18K/8K)≠((Offset)+Length_to_Delete)=((18K+21K)/8K)なので、削除は単一のチャンクでは起こらない。削除後、元のファイルシステムに7つのチャンクがある場合、元のチャンク5は新しいチャンク5ともう一つのチャンク、例えばチャンク8に変わる。新しいチャンク5ではStartBlockNumberは変わらない。ステップ1116において、(Offset%BlockSize)=(18K%8K)=2≠0なので、((Offset/BlockSize)+1)は新しいチャンク5のTotalBlockNumberであり、これは3ブロックに変わる。新しいチャンク5のPreviousChunkNumberは元のチャンク5のそれと同じである。NextChunkNumberはチャンク8に変わる。新しいチャンク5のPreviousChunkNumberは元のチャンク5のそれと同じである。新しいチャンク5のUnusedSizeInLastBlockはBlockSize−(Offset%BlockSize)=8K−(18%8)K=8K−2K=6Kバイトである。] [0050] チャンク8について、StartBlockNumberは、新しいチャンク5のStartBlockNumberに(Offset+Length_to_Delete)/BlockSizeを加えたものであり、これは10+(18K+21K)/8K=10+4=14であり、すなわちブロック14である。TotalBlockNumberは元のチャンク5のTotalBlockNumberから(Offset+Length_to_Delete)/BlockSizeを差し引いたものである。すなわち、6−4=2であり、チャンク8には2ブロックがある。チャンク8のPreviousChunkNumberはチャンク5であり、NextChunkNumberはチャンク6である。チャンク8のUnusedSizeInFirstBlockは(Offset+Length_to_Delete)%BlockSize=(18+21)%8=7Kバイトであり、UnusedSizeInLastBlockは元のチャンク5と同じサイズであり、4Kバイトである。ブロック13はファイルシステムから完全に削除されるので、このスペースは解放される。] [0051] 上記のファイルシステムは、セットトップボックスその他の装置のPVRファイルシステムであってもよい。] [0052] 実施形態を説明した。しかし、言うまでもなく様々な修正を行うことができる。また、当業者には言うまでもないが、開示した構成やプロセスを他の構成やプロセスで置き換えてもよく、その結果の実施形態が少なくとも実質的に同じ機能を果たし、少なくとも実質的に同じように、開示した実施形態と実質的に同じ結果を達成する。したがって、これらの実施形態やその他の実施形態が本出願では想定されており、特許請求の範囲に入る。]
权利要求:
請求項1 ファイルシステムにおけるファイルのデータ管理方法であって、前記ファイルのデータを格納する記憶スペースはサイズが同じで順次に付番された複数のブロックに分割され、前記ブロックは順次に付番されたチャンクにより構成され、各チャンクは少なくとも1つのブロックを有し、前記方法は、前記ファイル中のデータを削除する段階の後に、第1の管理データと第2の管理データとを用いて、各チャンクの前記最初のブロックの先頭部分と、前記最後のブロックの終わり部分とにある、データにより占有されていないスペースのサイズを記録する段階を有し、前記スペースのサイズは前記ブロックのサイズより小さいことを特徴とする、方法。 請求項2 前記削除する段階は、前記チャンクの先頭部分または終わりの部分からデータを削除する段階を有する、請求項1に記載の方法。 請求項3 ファイルのデータを有する複数のチャンクがリンクされ、リンク情報がファイルシステム管理データに記録される、請求項1または2に記載の方法。 請求項4 1つのチャンクが完全に削除されたとき、削除されたチャンクの記憶スペースを解放し、削除されたチャンクの前と後のチャンクをリンクする、請求項1ないし3いずれか一項に記載の方法。 請求項5 前記ファイルの一部が削除され、その削除の開始位置と終了位置とが同一ブロックではないが同一チャンク中にあるとき、前記チャンクを新しい第1のチャンクと新しい第2のチャンクとに分割し、第3の管理データと第4の管理データとを用いて、前記新しい第2のチャンクの最初のブロックの先頭部分と最後のブロックの終わりの部分との空のスペースのサイズを記録し、前記新しい第1のチャンクと新しい第2のチャンクとをリンクして前記ファイルの連続性を保つ段階をさらに有する、請求項1に記載の方法。 請求項6 前記新しい第1のチャンクは削除前の最初のチャンクの番号を用いて付番され、前記新しい第2のチャンクは前記ファイルシステムの元の最後のチャンクに続く付番をされる、請求項5に記載の方法。 請求項7 1つのブロックのデータを完全に削除したとき、前記ブロックのスペースを解放する、請求項5または6に記載の方法。 請求項8 請求項1に記載のファイルシステムにおけるファイルのデータ管理方法であって、前記ファイルのデータの一部を1つのチャンクの1つのブロックの途中から削除したとき、前記ブロックの削除されたデータに続くデータの残っている後半を前記ブロックのデータの前半の直後の位置に移動する段階と、前記チャンク中の削除をしたブロックとその前のブロックとを新しい第1のチャンクとして再構成し、削除をしたブロックの後にブロックがあれば、そのブロックを新しい第2のチャンクとして再構成する段階と、第3の管理データと第4の管理データとを用いて、前記新しい第2のチャンク中の最初のブロックの先頭部分と、最後のブロックの終わりの部分との空きスペースのサイズをそれぞれ記録する段階と、前記新しい第1のチャンクと新しい第2のチャンクとをリンクする段階とを有する、方法。 請求項9 前記新しい第1のチャンクは削除前の最初のチャンクの番号を用いて付番され、前記新しい第2のチャンクは前記ファイルシステムの元の最後のチャンクに続く付番をされる、請求項8に記載の方法。 請求項10 ファイルシステム管理データに前記チャンクのリンク情報を記録する、請求項8または9に記載の方法。 請求項11 ファイルのデータを格納する記憶スペースが、サイズが同じで順次に付番された複数のブロックに分割されたファイルシステムであって、前記ブロックは順次に付番されたチャンクにより構成され、各チャンクは少なくとも1つのブロックを有し、前記ファイルシステムは、各チャンクの先頭部分及び/または終わり部分の空き記憶スペースのサイズを示す、そのチャンクの管理データであって、前記空き記憶スペースはブロックのサイズより小さい管理データを有することを特徴とする、ファイルシステム。 請求項12 前記チャンクの最初のブロックの先頭部分と最後のブロックの終わり部分のスペースのサイズを、第1の管理データと第2の管理データにより記録する、請求項11に記載のファイルシステム。 請求項13 ファイルの全チャンクがリンクされて前記ファイルの連続性を保ち、リンク情報をファイルシステム管理データに記録する、請求項12に記載のファイルシステム。 請求項14 請求項11乃至13に記載のいずれかのファイルシステムを含む記憶装置。
类似技术:
公开号 | 公开日 | 专利标题 JP5954751B2|2016-07-20|テープ上のデータをロールバックする方法及びファイルシステム US5813011A|1998-09-22|Storage of a compressed file containing its own compression management table US7155566B2|2006-12-26|Information recording medium, information recording method, information recording apparatus, information reproduction method, and information reproduction apparatus US6023552A|2000-02-08|Data recording system RU2242805C2|2004-12-20|Способ записи, способ управления и устройство для записи JP4588411B2|2010-12-01|データを記録し且つ記録データを回復するための方法及び装置 ES2234304T3|2005-06-16|Sistemas de archivo que soportan la contaminacion de datos. DE69920277T2|2005-09-22|Gerät zur echtzeitigen Aufzeichnung und Wiedergabe EP0971358B1|2005-12-21|Data processing apparatus and file management method therefor JP4335492B2|2009-09-30|動画像管理方法及び装置 US8549051B2|2013-10-01|Unlimited file system snapshots and clones US7065535B2|2006-06-20|Methods and devices for recording or reading files on/from a sequential medium and sequential medium JP5265113B2|2013-08-14|データ処理装置 CN100530410C|2009-08-19|数据记录方法、数据显示方法和记录装置 TWI450110B|2014-08-21|用於直接大量儲存裝置檔案索引之方法、電腦可讀取媒體及系統 US7320012B2|2008-01-15|Method and apparatus for file management EP0857345B1|2002-11-06|Verfahren und schaltungsanordnung zur speicherung von diktaten bei einem digitalen diktiergerät US5717951A|1998-02-10|Method for storing and retrieving information on a magnetic storage medium via data blocks of variable sizes KR100854954B1|2008-08-28|저장매체 상의 데이터를 저장 및 판독하는 방법 및 장치와저장매체 US7308191B2|2007-12-11|Method for temporary deletion, search, restoration, and permanent deletion of stream object and a recording medium for storing additional information for restoration of stream object divided by temporary deletion JP4452363B2|2010-04-21|ファイルシステム KR100546524B1|2006-01-26|파일 관리 방법 US7398352B2|2008-07-08|Recording method and recording apparatus that limits number of rewrites to the same storage area US20050157599A1|2005-07-21|Data recording method, data recording device, data recording medium, data reproduction method, and data reproduction device US8010505B2|2011-08-30|Efficient backup data retrieval
同族专利:
公开号 | 公开日 CN101911198A|2010-12-08| US20100287218A1|2010-11-11| JP5394394B2|2014-01-22| WO2009083337A1|2009-07-09| EP2225757A1|2010-09-08| KR101531733B1|2015-06-25| US8825723B2|2014-09-02| EP2075796A1|2009-07-01| KR20100099216A|2010-09-10| CN101911198B|2013-02-20|
引用文献:
公开号 | 申请日 | 公开日 | 申请人 | 专利标题
法律状态:
2011-11-15| A621| Written request for application examination|Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20111114 | 2013-04-25| A977| Report on retrieval|Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20130425 | 2013-05-01| A131| Notification of reasons for refusal|Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20130430 | 2013-07-27| A521| Written amendment|Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20130726 | 2013-09-26| TRDD| Decision of grant or rejection written| 2013-10-02| A01| Written decision to grant a patent or to grant a registration (utility model)|Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20131001 | 2013-10-24| A61| First payment of annual fees (during grant procedure)|Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20131016 | 2013-10-25| R150| Certificate of patent or registration of utility model|Ref document number: 5394394 Country of ref document: JP Free format text: JAPANESE INTERMEDIATE CODE: R150 Free format text: JAPANESE INTERMEDIATE CODE: R150 | 2018-10-09| R250| Receipt of annual fees|Free format text: JAPANESE INTERMEDIATE CODE: R250 | 2019-10-25| LAPS| Cancellation because of no payment of annual fees|
优先权:
[返回顶部]
申请号 | 申请日 | 专利标题 相关专利
Sulfonates, polymers, resist compositions and patterning process
Washing machine
Washing machine
Device for fixture finishing and tension adjusting of membrane
Structure for Equipping Band in a Plane Cathode Ray Tube
Process for preparation of 7 alpha-carboxyl 9, 11-epoxy steroids and intermediates useful therein an
国家/地区
|